package paint_house;

/**
 * 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，
 * 你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
 * 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；
 * costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
 * 请你计算出粉刷完所有房子最少的花费成本。
 * @create: 2021-05-04 13:57
 **/
public class paint256 {
    public static void main(String[] args) {
        int[][] costs = new int[][]{{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
        int minCost = minCost(costs);
        System.out.println(minCost);
    }

    public static int minCost(int[][] costs) {
        int n = costs.length;
//        dp[i][j]代表第i号房子刷第j种颜色
//        int[][] dp = new int[n][3];

//        因为后面不再用到初始的数，直接在costs修改
        for (int i = 1; i < n; i++) {
            costs[i][0] = costs[i][0] + Math.min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] = costs[i][1] + Math.min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] = costs[i][2] + Math.min(costs[i - 1][0], costs[i - 1][1]);
        }
        return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1], costs[n - 1][2]));
    }
}
